package com.cat.dataStructure02;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/
 * @create 2025/10/28 20:34
 * @since JDK17
 */

public class Solution76 {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int n = matrix.length, m = matrix[0].length;
        for (int i = 0; i < n; i++) {
            heap.add(new int[] { matrix[i][0], i, 0 });
        }
        while (--k > 0) {
            var temp = heap.poll();
            int x = temp[1], y = temp[2];
            if (y + 1 < m) {
                heap.add(new int[] { matrix[x][y + 1], x, y + 1 });
            }
        }
        var t = heap.poll();
        return matrix[t[1]][t[2]];
    }
}
